%% header
%% \rightheader{Pendahuluan - \thepage}

\chapter{Pemrograman Dinamis}

Komputer adalah sebuah perangkat yang sengaja dibuat oleh manusia untuk membantu mereka dalam melakukan perhitungan matematis. Salah satu dari sekian banyak perhitungan matematis adalah perkalian matriks. Banyak sekali aplikasi yang melibatkan ribuan perkalian matriks, misalnya seperti animasi grafis. Secara sederhana bila kita ingin mengubah posisi sebuah bujursangkar dari satu lokasi dalam bidang datar ke lokasi lainnya (dengan kata lain membuat animasi sebuah bujursangkar yang bergerak), yang dilakukan oleh komputer adalah melakukan serangkaian perkalian matriks terhadap titik-titik koordinat bujursangkar tersebut.
Masih banyak lagi aplikasi lain yang melibatkan perkalian matriks.

Persoalan perkalian matriks dalam ilmu informatika digolongkan ke dalam masalah Pemrograman Dinamis (\emph{Dynamic Programming}). Teknik Pemrograman Dinamis berusaha memecahkan permasalahan ke dalam langkah-langkah yang membagi (\emph{divide}) masalah utama menjadi bagian-bagian kecil. Bagian-bagian kecil ini kemudian dicoba untuk diselesaikan dengan cara yang lebih mudah (\emph{conquer}). Namun demikian, walaupun menggunakan pendekatan yang mirip, teknik Pemrograman Dinamis memiliki karakteristik yang berbeda dengan teknik \emph{Divide and Conquer} yang biasa. Nanti akan kita lihat bahwa pembagian masalah ke dalam masalah-masalah yang lebih kecil itu, dalam Pemrograman Dinamis disebut dengan \emph{subproblems}.


\section{Sifat Perkalian Matriks}

Untuk sekedar menyegarkan ingatan, kita bahas sedikit tentang sifat-sifat perkalian matriks.

\subsection{Kesamaan Dimensi}

Bila seseorang ingin mengalikan dua buah matriks \(M_a\) dan \(M_b\), syarat pertama yang harus dipenuhi adalah dimensi kolom dari matriks \(M_a\) harus sama dengan dimensi baris dari matriks \(M_b\). Bila hal ini tidak dipenuhi, maka perkalian kedua buah matriks tidak dapat dilakukan. Mengapa hal ini terjadi? Karena demikianlah definisi operasi perkalian dari dua buah matriks.

\begin{equation}
\begin{array}{cc}
	M_a & M_b \\
	p \times q & q \times r \\
\end{array}
\end{equation}
Misalkan matriks \(M_a\) memiliki ukuran baris dan kolom \(p \times q\), sedangkan matriks \(M_b\) memiliki dimensi \(q \times r\), maka perkalian antara kedua matriks tersebut dapat dilakukan. Hasil perkalian kedua matriks ini adalah sebuah matriks baru \(M_c\) yang memiliki dimensi \(p \times r\).

\subsection{Definisi Perkalian Matriks}

Dua buah matriks \(M_a\) dan \(M_b\) yang masing-masing memiliki elemen-elemen seperti diilustrasikan di bawah ini, akan membutuhkan perkalian skalar sebanyak \(p \times q \times r\).
\begin{equation}\label{eq:perkalian-umum-matriks}
  \left(
\begin{array}{cccc}
	a_{1,1} & a_{1,2} & \ldots & a_{1,q} \\
	a_{2,1} & a_{2,2} & \ldots & a_{2,q} \\
	\vdots  & & \ddots & \vdots \\
	a_{p,1} & a_{p,2} & \ldots & a_{p,q} \\
\end{array}
  \right)
  \times
  \left(
\begin{array}{cccc}
	b_{1,1} & b_{1,2} & \ldots & b_{1,r} \\
	b_{2,1} & b_{2,2} & \ldots & b_{2,r} \\
	\vdots  & & \ddots & \vdots \\
	b_{q,1} & b_{q,2} & \ldots & b_{q,r} \\
\end{array}
  \right)
\end{equation}
Perkalian matriks pada Persamaan~\ref{eq:perkalian-umum-matriks} akan menghasilkan sebuah matriks baru \(M_c\) yang elemen-elemennya adalah seperti pada Persamaan~\ref{eq:hasil-perkalian-umum-matriks} berikut ini:
\begin{equation}\label{eq:hasil-perkalian-umum-matriks}
  \left(
\begin{array}{ccc}
	a_{1,1} \cdot b_{1,1} + a_{1,2} \cdot b_{2,1} + \ldots + a_{1,q} \cdot b_{q,1}
	  & \ldots
	  & a_{1,1} \cdot b_{1,r} + a_{1,2} \cdot b_{2,r} + \ldots + a_{1,q} \cdot b_{q,r} \\
	a_{2,1} \cdot b_{1,2} + a_{2,2} \cdot b_{2,2} + \ldots + a_{2,q} \cdot b_{q,2}
	  & \ldots
	  & a_{2,1} \cdot b_{2,r} + a_{2,2} \cdot b_{2,r} + \ldots + a_{2,q} \cdot b_{q,r} \\
	\vdots  & \ddots & \vdots \\
	a_{p,1} \cdot b_{1,1} + a_{p,2} \cdot b_{2,1} + \ldots + a_{p,q} \cdot b_{q,r}
	  & \ldots
	  & a_{p,1} \cdot b_{1,r} + a_{p,2} \cdot b_{2,r} + \ldots + a_{p,q} \cdot b_{q,r} \\
\end{array}
  \right)
\end{equation}
Seperti dapat kita lihat, setiap elemen dalam matriks \(M_c\) dihasilkan dari \(q\) buah perkalian skalar antara elemen-elemen matriks \(M_a\) sepanjang barisnya (ada \(q\) elemen) dan elemen-elemen matriks \(M_b\) sepanjang kolomnya. Keseluruhan elemen matriks \(M_c\) ada \(p \times r\) buah, yang masing-masingnya melibatkan \(q\) perkalian skalar. Sehingga total perkalian skalar yang diperlukan untuk mengalikan dua matriks \(M_a\) yang berukuran \(p \times q\) dan matriks \(M_b\) yang berukuran \(q \times r\) adalah \(p \times r \times q\).

\subsection{Asosiatifitas}

Perkalian matriks yang melibatkan lebih dari dua buah matriks memiliki sifat asosiatif. Sifat asosiatif dari perkalian mengatakan bahwa urutan pengerjaan perkalian tidak berpengaruh terhadap hasil perkalian, bagaimanapun urutan perkalian dikerjakan, hasil akhirnya akan selalu sama. Hal ini juga berlaku pada perkalian skalar antara bilangan-bilangan nyata.

Bila kita memiliki tiga buah matriks \(M_a\), \(M_b\), dan \(M_c\), maka berlaku sifat asosiatif berikut ini:

\begin{equation}
	M_a \times ( M_b \times M_c ) = ( M_a \times M_b ) \times M_c
\end{equation}


\section{Meminimalkan Perkalian Skalar}

Tujuan utama dari Pemrograman Dinamis pada masalah perkalian matriks adalah meminimalkan jumlah perkalian skalar yang diperlukan. Untuk memberikan gambaran tentang masalah ini, misalkan saja terdapat tiga matriks yang akan dikalikan dalam urutan \(A_1\), \(A_2\), dan \(A_3\). Misalkan saja ukuran dari masing-masing matriks tersebut adalah \(10 \times 100\), \(100 \times 5\), dan \(5 \times 50\). Berdasarkan sifat asosiatif perkalian matriks, kita dapat melakukan perkalian terhadap pasangan matriks \(A_1\) dan matriks \(A_2\) terlebih dahulu baru kemudian mengalikan matriks yang baru didapatkan dengan matriks \(A_3\). Sifat asosiatif menjamin bahwa hasil perkalian dengan urutan seperti ini juga akan sama dengan urutan perkalian \(A_2 \times A_3\) dan kemudian baru mengalikan matriks yang baru didapatkan dengan matriks \(A_1\).

Walaupun matriks akhir yang dihasilkan sama, namun kedua cara urutan perkalian tersebut melibatkan perkalian skalar yang jumlahnya jauh berbeda. Jika kita lakukan perkalian matriks dalam urutan \( (A_1 \times A_2 ) \times A_3\), berarti kita melakukan perkalian skalar sebanyak \(10 \cdot 100 \cdot 5 = 5000\) untuk pasangan matriks \(A_1\) dan matriks \(A_2\), ditambah perkalian skalar sebanyak \(10 \cdot 5 \cdot 50 = 2500\) untuk mengalikan matriks hasil perkalian \(A_1\) dan \(A_2\) sebelumnya dengan matriks \(A_3\). Total perkalian skalar yang diperlukan adalah \(5000 + 2500 = 7500\).

Bila kita lakukan perkalian matriks dengan urutan yang berbeda, yaitu \( A_1 \times ( A_2 \times A_3) \), kita memerlukan perkalian skalar sebanyak \(100 \cdot 5 \cdot 50 = 25000\) dan \(10 \cdot 100 \cdot 50 = 50000\) buah, total sebanyak \(25000 + 50000 = 75000\) perkalian skalar. Dari contoh sederhana ini, kita ketahui bahwa susunan urutan perkalian matriks yang berbeda akan melibatkan perkalian skalar yang jumlahnya bisa sangat jauh berbeda. Dalam contoh ini urutan pengerjaan cara pertama memerlukan waktu 10 kali lebih cepat daripada urutan pengerjaan cara kedua.

\textbf{\emph{Matrix-chain multiplication problem}} (``Masalah perkalian rantai-matriks'') dapat dinyatakan sebagai berikut: diketahui rangkaian \(\langle A_1, A_2, \ldots A_n \rangle\) matriks, di mana untuk harga \(i = 1, 2, \ldots n\), matriks \(A_i\) memiliki dimensi \(p_{i-1} \times p_i\), letakkan tanda kurung di antara rangkaian matriks tersebut sehingga jumlah perkalian skalar yang dibutuhkan menjadi minimum.

\section{Pendekatan Pemrograman Dinamis}

Sebuah algoritma yang dikatakan memiliki sifat Pemrograman Dinamis dapat dibagi menjadi empat tahapan berikut:
\begin{enumerate}
	\item Mengkarakterisasikan struktur dari solusi optimal.
	\item Secara rekursif mendefinisikan nilai dari solusi optimal.
	\item Menghitung nilai dari solusi optimal secara \emph{bottom-up}.
	\item Membangun solusi optimal dari informasi yang telah dihitung.
\end{enumerate}
Kita lihat lebih jauh bagaimana tahapan-tahapan tersebut diterapkan dalam mencari pemecahan terhadap ``Masalah perkalian rantai-matriks'' berikut ini.


\section{Algoritma Matrix-Chain-Multiplication}

Gambar~\ref{alg:alg-matrix-chain-order} \cite{cormen} menunjukkan
langkah-langkah yang dilakukan dengan menggunakan pendekatan
\emph{dynamic programming}. Untuk mengetahui jumlah perkalian skalar
yang minimum, kita melakukan pendekatan \emph{bottom-up}. Dari setiap
pasangan matriks kita dapat mengetahui ongkos optimum (jumlah
perkalian skalar minimum) dan menyimpannya dalam sebuah struktur data.
Algoritma dalam Gambar~\ref{alg:alg-matrix-chain-order} mengasumsikan
sejumlah matriks \(A_i\) yang memiliki dimensi \(p_{i-1} \times p_i\)
untuk setiap nilai \(i = 1, 2, \ldots, n\). Masukan bagi algoritma
tersebut adalah deretan \(p_0, p_1, p_2, \ldots, p_n\) dengan
\emph{length}(\(p\)) \(= n+1\). Lebih lanjut algoritma ini menggunakan
bantuan tabel \(m[1 \ldots n, 1 \ldots n]\) untuk menyimpan ongkos
\(m_{i,j}\) dan bantuan tabel \(s[1 \ldots n, 1 \ldots n]\) yang
mencatat indeks \(k\) yang bisa menghasilkan ongkos optimum untuk
menghitung \(m_{i,j}\). Tabel \(m\) dan \(s\) jika divisualisasikan
tampak seperti dalam Gambar~\ref{fig:tabel-m} dan
Gambar~\ref{fig:tabel-s}.

\begin{algorithm}
\begin{algorithmic}[1]
  \REQUIRE \(p\), larik berisi dimensi-dimensi matriks
  \STATE \textsc{Matrix-Chain-Order (\(p\))}
  \STATE \(n \leftarrow\) length[\(p\)] - 1
  \FOR{\(i \leftarrow 1\) to \(n\)}
    \STATE \(m_{i,i} \leftarrow 0\)
  \ENDFOR
  \FOR{\(l \leftarrow 2\) to \(n\)}
    \FOR{\(i \leftarrow 1\) to \(n - l + 1\)}
      \STATE \(j \leftarrow i + l - 1\)
      \STATE \(m_{i,j} \leftarrow \infty\)
      \FOR{\(k \leftarrow i\) to \(j - 1\)}
        \STATE \(q \leftarrow m_{i,k} + m_{k+1,j} + p_{i-1} p_k p_j \)
        \IF{\(q < m_{i,j}\)}
          \STATE \(m_{i,j} \leftarrow q\)
          \STATE \(s_{i,j} \leftarrow k\)
        \ENDIF
      \ENDFOR
    \ENDFOR
  \ENDFOR
  \STATE return \(m\) and \(s\)
\end{algorithmic}
\caption{Algoritma Matrix-Chain-Order~\cite{cormen}}
\label{alg:alg-matrix-chain-order}
\end{algorithm}

Baris 3 sampai 5 dari Algoritma~\ref{alg:alg-matrix-chain-order}
menginisialisasi isi dari tabel \(m\) dengan nilai 0 untuk nilai-nilai
\(j\) yang sama dengan \(i\). Entri \(m_{i,j}\) nantinya akan berisi
jumlah minimum perkalian skalar yang dibutuhkan untuk melakukan
perkalian matriks-matriks \(A_i\) sampai \(A_j\). Untuk sebuah matriks
tunggal, sama sekali tidak diperlukan satu pun perkalian skalar.
Karena itu entri \(m_{i,j}\) diisi dengan nilai 0.

\begin{figure}
{\par\centering
  \includegraphics{TabelM}
\par}
\caption[Tabel $m$]{Isi tabel $m$ setelah lengkap diisi.
  Data dalam
  tabel ini diturunkan dari matriks-matriks pada
    Tabel~\ref{tbl:contoh-matriks} dan menggunakan
    Algoritma~\ref{alg:alg-matrix-chain-order}. Baris paling bawah
    pada tabel $m$ ini diisi ketika
    Algoritma~\ref{alg:alg-matrix-chain-order} menginisialisasinya
    pertama kali.}
\label{fig:tabel-m}
\end{figure}

\begin{figure}
{\par\centering
  \includegraphics{TabelS}
\par}
\caption[Tabel $s$]{Isi tabel $s$ setelah lengkap diisi. Data dalam
  tabel ini diturunkan dari matriks-matriks pada
    Tabel~\ref{tbl:contoh-matriks}
  (Halaman~\pageref{tbl:contoh-matriks}) dan menggunakan
    Algoritma~\ref{alg:alg-matrix-chain-order}. Baris paling bawah
    pada tabel $s$ ini diisi ketika
    Algoritma~\ref{alg:alg-matrix-chain-order} menginisialisasinya
    pertama kali.}
\label{fig:tabel-s}
\end{figure}

Baris-baris secara sistematis mengisi entri-entri tabel \(m_{i,j}\)
  dengan data yang sesuai. Baris 9 menginisialisasi entri \(m_{i,j}\)
  dengan nilai \(\infty\) karena nantinya entri ini akan dibandingkan
  dengan nilai yang lebih kecil pada loop terdalam (baris 10 sampai
      16). Baris 11 menghitung jumlah perkalian skalar yang diperlukan
  untuk mengalikan matriks-matriks \(A_i\) sampai \(A_j\) dengan
  `memotong' perkalian matriks pada matriks \(A_k\)
\[ ( A_i \times A_{i+1} \times A_{i+2} \times \ldots \times A_{k-1}
    \times A_k ) \times ( A_{k+1} \times \ldots A_{j-1} \times A_j )
  \]
Setiap kali iterasi pada variabel \(k\), letak `pemotongan' perkalian
matriks juga digeser sesuai dengan harga \(k\). Dalam setiap kali
iterasi, jumlah perkalian skalar yang dibutuhkan dicatat di dalam
variabel \(q\). Harga \(q\) akan selalu dibandingkan dengan nilai di
dalam entri \(m_{i,j}\).

Loop terdalam pada baris 10 - 16 sebetulnya sama dengan mencari nilai
perkalian skalar minimum dari semua kemungkinan yang ada.

\[
m_{i,j} = \left\{
\begin{array}{lc}
	0 & \mathrm{if} \ i = j , \\
	\min_{i \leq k < j} \{ m_{i,k} + m_{k+1,j} + p_{i-1} p_k p_j \} & \mathrm{if} \ i < j \\
\end{array}
\right.
\]

Setiap kali berhasil menemukan nilai perkalian skalar yang lebih kecil
daripada yang sudah tercatat dalam entri \(m_{i,j}\), entri tabel
\(s_{i,j}\) dimutakhirkan dengan nilai \(k\). Maksudnya tidak lain
adalah mencatat di mana `pemotongan' harus dilakukan.

Ketika Algoritma~\ref{alg:alg-matrix-chain-order} diterapkan untuk 6
buah matriks seperti dalam Tabel~\ref{tbl:contoh-matriks}, maka isi
tabel \(m\) dan \(s\) akan tampak seperti dalam
Gambar~\ref{fig:tabel-m} dan~\ref{fig:tabel-s}. Ujilah
pemahaman anda tentang uraian yang diberikan dalam subbab ini dengan
mengisi tabel \(m\) dan \(s\) milik anda sendiri, kemudian
membandingkannya dengan gambar yang tersedia.

\begin{table}
\caption{Enam matriks contoh untuk Gambar~\ref{fig:tabel-m}
  dan~\ref{fig:tabel-s}.}
\label{tbl:contoh-matriks}
{\par\centering
\begin{tabular}{|c|r@{$\times$}l|}
  \hline
    Matriks & \multicolumn{2}{c|}{Dimensi} \\
  \hline
  \hline
    \(A_1\) & \(5\) & \(10\) \\
    \(A_2\) & \(10\) & \(12\) \\
    \(A_3\) & \(12\) & \(3\) \\
    \(A_4\) & \(3\) & \(50\) \\
    \(A_5\) & \(50\) & \(7\) \\
    \(A_6\) & \(7\) & \(5\) \\
  \hline
\end{tabular}
\par}
\end{table}

Telah disebutkan sebelumnya, keluaran dari
Algoritma~\ref{alg:alg-matrix-chain-order} adalah tabel \(m\) yang
berisi informasi tentang jumlah perkalian skalar minimum yang
didapatkan untuk mengalikan matriks-matriks yang diberikan. Di samping
itu, algoritma tersebut juga menghasilkan sebuah tabel \(s\), yang
berisi informasi tentang di mana tanda kurung harus diletakkan supaya
jumlah perkalian skalar yang dilakukan bisa minimum.

Untuk mengetahui bagaimana informasi dalam tabel \(s\) bisa
dimanfaatkan, kita lihat contoh pada Gambar~\ref{fig:tabel-s} yang
telah terisi lengkap. Data-data dalam tabel itu menginformasikan
kepada kita bagaimana kita harus meletakkan kurung di antara 6
matriks yang diberikan pada Tabel~\ref{tbl:contoh-matriks}. Karena
kita memiliki enam buah matriks, maka kita harus tahu bagaimana
pengelompokan keenam buah matriks ini harus dilakukan. Untuk itu kita
lihat entri \(s_{1,6}\) pada tabel \(s\). Entri ini bernilai 3. Itu
artinya, untuk menghasilkan perkalian skalar dalam jumlah yang
minimum, matriks-matriks \(A_1\) sampai dengan \(A_6\) harus
`dipotong' menjadi 2 kelompok, dan perpotongannya terletak pada
matriks \(A_3\):
\[ ( A_1 \times A_2 \times A_3 ) \times ( A_4 \times A_5 \times A_6) \]
Lebih lanjut harus dicari bagaimana kelompok matriks \(A_1\), \(A_2\),
dan \(A_3\) dikelompokkan. Untuk itu lihat entri \(s_{1,3}\), yang
ternyata bernilai 1. Ini artinya perkalian matriks harus lebih dulu
mengerjakan perkalian matriks \(A_2\) dengan \(A_3\), baru kemudian
hasilnya dikalikan dengan \(A_1\).

Demikian juga halnya dengan kelompok matriks \(A_4\) sampai \(A_6\),
sehingga hasil akhir pengelompokan matriks yang dihasilkan adalah:

\[ ( (A_1) \times ( (A_2) \times (A_3) ) ) \times ( ( (A_4) \times
      (A_5) ) \times (A_6) ) \]
